package com.example.demo.demos.web;

import org.springframework.stereotype.Component;

/**
 * 二分查找法
 */
@Component
public class Arithmetic {

    Arithmetic() {

    }

    /**
     *
     * @param a 待查找的数组
     * @param target 待查找的目标值
     * @return  找到返回目标索引，找不到返回-1
     */
    public static int dichotomySearch(int [] a, int target) {

        int i = 0;  //从下标0开始查找
        int j = a.length - 1;   //数组长度
        while (i <= j) {    //查找范围内有值进入循环
            int m = (i + j) >>> 1;    //中间索引  将数组一分为二确定中间位置
            if (target < a[m]) { //待查找的目标值在左边
                j = m - 1;      //可以理解为 2 5 1 3 4 从中间值 1 的位置向左开始查询，即 5 2
            } else if (a[m] < target) { //待查找的目标值在右边
                i = m + 1;      //可以理解为 2 5 1 3 4 从中间值 1 的位置向右开始查询，即 3 4
            } else {
                return m;       //找到目标值后返回索引位置
            }
        }

        return -1;
    }

    /**
     *  二分查找法进阶版
     * @param a 待查找的数组
     * @param target 待查找的目标值
     * @return  找到返回目标索引，找不到返回-1
     */
    public static int dichotomySearchAdvanced(int [] a, int target) {

        int i = 0;
        int j = a.length;   //（第一处改动）
        while (i < j) {    //（第二处改动）
            int m = (i + j) >>> 1;    //中间索引  将数组一分为二确定中间位置
            if (target < a[m]) { //待查找的目标值在左边
                j = m;          //（第三处改动）此时j的位置 一定不是查找目标
            } else if (a[m] < target) { //待查找的目标值在右边
                i = m + 1;      //可以理解为 2 5 1 3 4 从中间值 1 的位置向右开始查询，即 3 4
            } else {
                return m;       //找到目标值后返回索引位置
            }
        }

        return -1;
    }

    /**
     *     左移运算符“<<” - 使指定值的所有位都左移规定的次数。
     *     左移m<<n 代表把数字m在无溢出的前提下乘以2的n次方。
     *
     *     例如，5<<3 就是5乘以2的3次方，结果是40。
     *
     *     右移运算符“>>” - 使指定值的所有位都右移规定的次数。
     *     右移m>>n 代表把数字m除以2的n次方，原来是正数的还是正数，负数还是负数。注意，如果是单数，也就是二进制末位为1，则结果是将m除以2的n次方的整数商。
     *
     *     例如，16>>3 就是16除以2的3次方，结果是2。
     *     15>>3 就是14(15-1)除以2的3次方，结果是1。
     * @param args
     */
    public static void main(String[] args) {
//        System.out.println(5 << 1);
//        System.out.println(5 << 2);
//        System.out.println(5 << 3);
//
//        System.out.println(16 >> 1);
//        System.out.println(16 >> 2);
//        System.out.println(16 >> 3);
        int[] a = {15,23,38,47,55,62,88,95,102,123};
        int i = dichotomySearch(a, 95);
        //分别和55、95进行了比较
        System.out.println(i);
    }
}
